/*
 * UNIVERSIDAD DEL VALLE DE GUATEMALA
 * ALGORITMOS Y ESTRUCTURAS DE DATOS
 * JOSUE BARRIENTOS - 09049
 * 
 * 
 * EL PROGRAMA TOMA UNA CADENA DESDE LA CONSOLA Y LA CREA SU CODIGO DE HUFFMAN. 
 * DESPLIEGA EL CODIGO Y EL MENSAJE CODIFICADO. DESPUES TOMA UN MENSAJE EN CODIGO Y
 * LO DECODIFICA PARA MOSTRARLO EN LETRAS.
 * 
 * LA CLASE BINARYTREE SE TOMO DEL LIBRO. LAS OTRAS CLASES DEL PAQUETE STRUCTURE5
 * SON REQUERIDAS PARA BINARYTREE. 
 * 
 * LA CLASE BINARYHEAP SE TOMO DE: 
 * http://www.java-tips.org/java-se-tips/java.lang/priority-queue-binary-heap-implementation-in-3.html
 * LAS CALSES PRIORITYQUEUE Y UNDERFLOWEXCEPTION SON NECESARIAS PARA ESTA.  * 
 * 
 */
package ht6;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import structure5.BTInorderIterator;
import structure5.BinaryTree;

/**
 *
 * @author Casa
 */
public class HT6 {
    
    static String txt_code;
    static String txt_decode;
    static String txt_gen="";
    static String code_gen;
    static BinaryTree<String> arbol_huffman=null;
    static BinaryHeap monticulo=new BinaryHeap();
    static Map<Character, Integer> letras;
    static Map<String, String> codificacion;
    static Map<String, String> invertido;

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        
        System.out.println("HOJA DE TRABAJO 6 - CODIFICACION HUFFMAN");
        System.out.print("\nINGRESE MENSAJE: ");
        
       txt_code = get_input();
                   
        crear_arbol_huffman();
        codificar(arbol_huffman.root());                
        generar_tablas();                
        desplegar_codificacion();        
        
        System.out.print("EL MENSAJE EN CODIGO ES: ");
        desplegar_mensaje_en_codigo();        

        System.out.print("\n\nINGRESE MENSAJE UTILIZANDO CODIFICACION: ");
        txt_decode=get_input();          
        
        decodificar(txt_decode, "");
        System.out.println("EL MENSAJE ES: " + txt_gen);
        
    }

    /**
     *
     * @param arbol
     */
    public static String get_input(){
       String cadena = "";
       //  open up standard input
        BufferedReader buff = new BufferedReader(new InputStreamReader(System.in));
        try {
            cadena = buff.readLine();
         } catch (IOException ioe) {
           System.out.println("ERROR VUELVA A INTENTAR");
            System.exit(1);
        }   
        return cadena;
    }   
        
    /**
     *
     * @param arbol
     */
    public static void crear_arbol_huffman(){
        letras= new HashMap(txt_code.length()/2);  
        
        for(char c : txt_code.toCharArray()) {
            if (letras.containsKey(c)==false){
                letras.put(c, 1);
            }
            else{
                letras.put(c,  letras.get(c)+1);
            }
        } 
                
        int i=0;
        Iterator cualquier=letras.entrySet().iterator();
        while (cualquier.hasNext()){
            Entry n=  (Entry) cualquier.next();
            monticulo.insert(new BinaryTree(String.valueOf(n.getKey()),(Integer) n.getValue()));
            i++;
        }
                                 
        while (monticulo.size()!=1){            
            BinaryTree<String>  der= (BinaryTree) monticulo.deleteMin();
            BinaryTree<String>  izq= (BinaryTree) monticulo.deleteMin();
            arbol_huffman=new BinaryTree(der.value() + izq.value(), der.frecuencia()+izq.frecuencia(), izq, der);
            monticulo.insert(arbol_huffman);
	}             
    }
        
    /**
     *
     * @param arbol
     */
    public static void codificar(BinaryTree<String> arbol){
        if (!arbol.left().isEmpty()){ 
            arbol.left().setCodigo(arbol.codigo()+ "1");
            codificar(arbol.left());
     
        }
        if (!arbol.right().isEmpty()){
            arbol.right().setCodigo(arbol.codigo()+ "0");
            codificar(arbol.right());
               
        }
    }
    
    /**
     *
     * @param arbol
     */
    public static void generar_tablas(){
        codificacion= new HashMap(arbol_huffman.size());
        invertido= new HashMap(arbol_huffman.size());
        BTInorderIterator<String> itera = (BTInorderIterator<String>) arbol_huffman.inorderIterator();
        while (itera.hasNext()){
            BinaryTree<String> n = itera.siguiente();
            if (n.value().length()==1){
                codificacion.put(n.value(), n.codigo());
                invertido.put(n.codigo(), n.value());
            }            
        }           
    }
    
    /**
     *
     * @param arbol
     */
    public static void desplegar_codificacion(){
        System.out.println("");
        System.out.println("LETRA - FRECUENCIA - CODIGO");
        Iterator cualquier2=codificacion.entrySet().iterator();
        while (cualquier2.hasNext()){
            Entry<String, String> s= (Entry) cualquier2.next();
            System.out.println("  " + s.getKey()+ "   -      " + letras.get( s.getKey().charAt(0) ) + "     -   "  + s.getValue());
        }           
    }
 
      
    /**
     *
     * @return
     */
    public static void desplegar_mensaje_en_codigo(){
        for(Character c : txt_code.toCharArray()) {
            System.out.print(codificacion.get(c.toString()));
            }
          }
        

     /**
     *
     * @return
     */
    public static void decodificar(String original, String temp){
        temp=temp+original.substring(0, 1);
        original=original.substring(1);
        if (invertido.containsKey(temp)){
            txt_gen=txt_gen+invertido.get(temp);
            temp="";
        }
        if (!original.equals("")){
            decodificar(original, temp);
        }        
        
    }
    
}
